/*
* INSANE - Interactive Structural Analysis Environment
*
* Copyright (C) 2003-2004
* Universidade Federal de Minas Gerais
* Escola de Engenharia
* Departamento de Engenharia de Estruturas
*
* Author's email : insane@dees.ufmg.br
* Author's Website : http://www.dees.ufmg.br/insane
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*
*/
package br.ufmg.dees.insane.util.xfem;

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;

import br.ufmg.dees.insane.util.IPoint3d;


/*
*                              T W O - D I M E N S I O N A L
*                              -----------------------------
*      F I N I T E   E L E M E N T   P A R T I T I O N I N G   B Y   A   S E G M E N T
*      -------------------------------------------------------------------------------
*
*                         N. Sukumar, University of California, Davis
*
*                                   C + +   C O D E
*                                   ---------------
*
* Purpose
* =======
* Partition a 2-dimensional finite element (triangle or quadrilateral) by a segment that
* is given by a point on it and its bi-normal (m) [t x m is a vector in the z-direction,
* where t is the tangent vector of the segment].  The nodal connectivities of the finite
* element are stored in counter-clockwise orientation (ccw). The finite element is 
* partitioned into 3-noded triangular elements on either side of the segment. Degenerate 
* cases are handled using a tolerance in the partitioning algorithm. This function is used
* in the application of the eXtended Finite Element Method (X-FEM) to crack modeling in
* 2-dimensions. A paper, which describes the partitioning algorithm can be found at
* http://dilbert.engr.ucdavis.edu/~suku/xfem/papers/xfem_cracks3d.pdf
*
* Author
* ======
* N. Sukumar, University of California, Davis
* E-mail: n-sukumar@ucdavis.edu
* First version: June 1999; Updated: August 2003
*
* Reference
* =========
* N. Sukumar, `Element partitioning code in 2-d and 3-d for the extended finite
* element method,' Available from http://dilbert.engr.ucdavis.edu/~suku/xfem, 2000
* 
* Algorithm
* =========
* A short description of the algorithm follows. The orientation of the nodes of the finite
* element are first set (ABOVE = +1, BELOW = -1, or ON = 0) using the segment (GxElement_c)
* that partitions the element. Partitioning is carried out if and only if there exists two 
* nodes with orientation = 1 and orientation = -1 in the connectivity. A loop over the edges 
* of the finite element is carried out, and if there is an intersection for an edge, the 
* point of intersection is computed and added to the node and face list. The orientation of 
* the point of interesection is +10 if the orientation of the first point of the edge is 1, 
* and -10 if the orientation of the first point is -1. This updates the edge lists of the 
* finite element. Now, using the edge lists of the finite element, two new edge lists for the 
* surfaces ABOVE and BELOW the (crack) segment are created.  The two edges (upper and lower) 
* that correspond to the (crack) segement are also created such that ccw orientation of the 
* nodes is preserved. The centroid of the two domains is evaluated with orientation = 1000 
* for the ABOVE surface and orientation = -1000 for BELOW surface. A loop over the two edge
* lists is performed and using the centroid for each surface, the partitioned elements are 
* obtained
*/

//Partitioning a 2D element that is cut by a (crack) segment into sub-elements (triangles) 
//for the purpose of numerical integration
/**
 * @author Kelson Wolff
 *
 */
public class Partitioning2D {
	
	static double tolerance = 1.0e-6;
	
	protected double pointX, pointY, pointZ;
	
	protected List<List> subElementsConnectAboveCrack;
	
	protected List<List> subElementsConnectBelowCrack;
	
	protected List<List> subElementsCoordsAboveCrack;
	
	protected List<List> subElementsCoordsBelowCrack;
	
	/**
 	 * 
	 */
	public Partitioning2D(String[] nodIncid, double[][] nodCoords, String[][] facIncid, 
						  int nNodes, int nFaces, int nNodesFace, 
						  double[] point, double[] normal) {
		int nbNodes = nNodes;           // no of nodes for the (XFEMElement) element

		int nbFaces = nFaces;           // no of faces (edges) of the XFEMElement

		int nbNodesFace = nNodesFace;   // no of nodes for a face (edge) of the XFEMElement

		int maxNodeId = nNodes;         // max node Id
		
		Map<String,Integer> connect = new HashMap<String,Integer>();	// vector to store the element connectivity
		List<String> connectMirror = new ArrayList<String>();
		
//		map definition, typedef, and const iterators for face ID to face connectivity
		List<String[]> Face = new ArrayList<String[]>();
		ListIterator itF;

		String[] facenodes = new String[nbNodesFace]; 	  // nodal connectivity for the face

//		map, typedef and const iterators for node ID to nodal coordinates
		List<double[]> Coord = new ArrayList<double[]>();
		ListIterator itC;
		
//		map definition, const iterators, and typedef for insertion for node ID to 
//		orientation
		List<String> Abo = new ArrayList<String>(); 
		ListIterator itO;
		
//		segment is given by its bi-normal m and a POINT p
		double[] p = point;
		double[] m = normal;
		
//		Initializations

		int i, j, k;
		double[] xyz = new double[3];
		double[] xyzvec = new double[3];
		String[] elemconnect = new String[nbNodes];
		String[][] v = new String[nbFaces][nbNodesFace];

//		node Id to nodal coordinates map & node Id to nodal coordinates map	
		for(i=0; i<nbNodes; i++){
			xyz[0] = nodCoords[i][0];
			xyz[1] = nodCoords[i][1];
			xyz[2] = nodCoords[i][2];
			double[] xyzAux = new double[3];
			xyzAux[0] = xyz[0];
			xyzAux[1] = xyz[1];
			xyzAux[2] = xyz[2];
			Coord.add(xyzAux);
			elemconnect[i] = nodIncid[i];
		}
		
		for(i=0; i<nbFaces; i++){
			for(j=0; j<nbNodesFace; j++){
				v[i][j] = facIncid[i][j];
			}
		}
		
////////PRINT		Coord		
		for(i=0; i<nbNodes; i++){
			double[] t1 = (double[]) Coord.get(i);
			for(j=0; j<3; j++){
				System.out.print(t1[j]+"  ");
			} 
			System.out.println();
		}
////////
		
//		element connectivity
		for (i = 0; i < nbNodes; ++i) {
			connect.put(elemconnect[i],i);
			connectMirror.add(elemconnect[i]);
		}
		
////////PRINT		connect
		for(i=0; i<nbNodes; i++){
			Integer t2 = connect.get(connectMirror.get(i));
			System.out.print(t2);
			System.out.println();
		}
////////
		
////////PRINT		connectMirror
		for(i=0; i<nbNodes; i++){
			String t3 = (String) connectMirror.get(i);
			System.out.print(t3);
			System.out.println();
		}
////////
		
//		face connectivity
		for (i = 0; i < nbFaces; ++i) {
			for (j = 0; j < nbNodesFace; ++j){
				facenodes[j] = v[i][j];
			}
			String[] facenodesAux = new String[nbNodesFace];
			for (k = 0; k < nbNodesFace; ++k){
				facenodesAux[k] = facenodes[k];
			}	
			Face.add(facenodesAux);
		}

////////PRINT		Face
		itF = Face.listIterator();
		while(itF.hasNext()){
			String[] t4 = (String[]) itF.next();
			for(i=0; i<nbNodesFace; i++){
				System.out.print(t4[i]+"  ");
			}
			System.out.println();
		}
////////
		
//		set the node Id to orientation map: if the node is above the crack (GxElement_c) segment,
//		orientation = 1, if the node is below the crack (GxElement_c) segment, orientation = -1,
//		and if the node is on the crack (GxElement_c) segment, orientation = 0
		
		double px, py, pz;
		String orient;
		
		itC = Coord.listIterator();
		while(itC.hasNext()){
			xyzvec = (double[]) itC.next();
			px = xyzvec[0]; py = xyzvec[1]; pz = xyzvec[2];
			orient = this.OnAboveOrBelow(px,py,pz,p,m);
			Abo.add((String)orient);
		}
		
////////PRINT		Abo
		itO = Abo.listIterator();
		while(itO.hasNext()){
			String t5 = (String) itO.next();
			System.out.println(t5);
		}
////////

//		check that the nodal orientation of at least two nodes is +1 and -1 in the connectivity 
//		list of the finite element; if not, then the crack line does not cut the element or is 
//		along an element edge. In either case, no partitioning of the elements into sub-elements
//		is required
		
		boolean partition = false;
		boolean nodeAbove = false;
		boolean nodeBelow = false;
		String orientation;
		itO = Abo.listIterator();
		while(itO.hasNext()){
			orientation = (String) itO.next();
			if(orientation.equals("below")) nodeBelow = true;
			if(orientation.equals("above")) nodeAbove = true;
		}
		if (nodeBelow && nodeAbove) partition = true;
		
//		if partition = true, at least one edge is cut by the (crack) segment; if not, then
//		no partitioning of the element is required and hence the function returns
		
		if (!partition) {
			System.out.println("\nELEMENT PARTIONING NOT REQUIRED\n");
//			return 1;
		}
		
//		loop over the edges to check edges that are cut by the (crack) segment
		
		boolean intersect;
		boolean isCut;
		String orient1, orient2;
		double p1x, p1y, p1z, p2x, p2y, p2z;
		
		List<String> NodesPoints = new ArrayList<String>();
		List<String[]> NewFaceConn = new ArrayList<String[]>();
		ListIterator itN = NewFaceConn.listIterator();
		int counter = 1; int connVectorSize = 0;
		
		itF = Face.listIterator();
		while (itF.hasNext()) {
			isCut = false;
			String[] edgenodes = new String[nbNodesFace];
			edgenodes = (String[]) itF.next();
//			(nbNodesFace) nodes per face/edge in 2D
			String initiFaceNode = edgenodes[0];
			String finalFaceNode = edgenodes[nbNodesFace-1];
			orient1 = (String) Abo.get(((Integer)connect.get(initiFaceNode)).intValue());
			orient2 = (String) Abo.get(((Integer)connect.get(finalFaceNode)).intValue());
			if ((orient1.equals("below") && orient2.equals("above")) ||
				(orient1.equals("above") && orient2.equals("below")))	isCut = true;		
			   	
//			for edges cut by the crack, find the intersection point
			
			if (isCut) {
				
				pointX = 0.0;	pointY = 0.0;	pointZ = 0.0;
				
				double[] xyzvec1 = (double[]) Coord.get(((Integer)connect.get(initiFaceNode)).intValue());
				p1x = xyzvec1[0]; p1y = xyzvec1[1]; p1z = xyzvec1[2];
				double[] xyzvec2 = (double[]) Coord.get(((Integer)connect.get(finalFaceNode)).intValue());
				p2x = xyzvec2[0]; p2y = xyzvec2[1]; p2z = xyzvec2[2];
							
//				pointX, pointY and pointZ are the coordinates of the intersection point
				
				intersect = LineIntersection(p1x,p1y,p1z,p2x,p2y,p2z,p,m);
				if (!intersect) assert false;
				
				double[] xyzvec3 = new double[3];
				xyzvec3[0] = pointX;	xyzvec3[1] = pointY; xyzvec3[2] = pointZ;
				
////////////////PRINT
				System.out.println("Intersection Point");
				for(i=0; i<3; i++) System.out.print(xyzvec3[i]+"   ");
				System.out.println();
////////////////				
				
//				insert the new point in the node/point orientation map: if the first node in the
//				connectivity for the point is above the crack segment, insert +10 for the orientation
//				and if the first node in the connectivity is below the crack plane, insert
//				-10 for the orientation
				
				orient = (orient1.equals("below")) ? "belowEdge" : "aboveEdge";
				String orientAux = new String();
				orientAux = orient;
				Abo.add(orientAux);
				
//				insert the new point coordinates in the node-coordinates map
				
				double[] xyzvectorAux = new double[3];
				xyzvectorAux[0] = xyzvec3[0]; xyzvectorAux[1] = xyzvec3[1]; xyzvectorAux[2] = xyzvec3[2];
				Coord.add(xyzvectorAux);  
				
//				insert previous node and the point (ID is maxNodeId) in the NEW connectivity list
		
				String newNodeLabel = new String();
				newNodeLabel = "intersection ".concat(String.valueOf((int)counter));
				counter++;
				NodesPoints.add(initiFaceNode);
				NodesPoints.add(newNodeLabel);
				NodesPoints.add(finalFaceNode);
				connVectorSize = 3;
				
				connectMirror.add(newNodeLabel);
				connect.put(newNodeLabel,maxNodeId);
				maxNodeId++;
			}
			
			else {
//				copy the edge to the new edge (no intersections)
				NodesPoints.add(initiFaceNode);
				NodesPoints.add(finalFaceNode);
				connVectorSize = 2;
			}
			String[] newEdgeNodes = new String[connVectorSize];
			for(i=0; i<newEdgeNodes.length; i++){
				newEdgeNodes[i] = NodesPoints.get(i);
			}
			NewFaceConn.add(newEdgeNodes); // itF->face ID
			NodesPoints.clear();
		}
		
////////PRINT
		counter = counter - 1;
		System.out.println("Number of cuted Edges = "+counter);
		System.out.println();
////////
		
////////PRINT		Abo New
		itO = Abo.listIterator();
		while(itO.hasNext()){
			String t6 = (String) itO.next();
			System.out.println(t6);
		}
		System.out.println();
////////
			
////////PRINT		Coord New
		itC = Coord.listIterator();
		while(itC.hasNext()){
			double[] t7 = (double[]) itC.next();
			for(i=0; i<3; i++) System.out.print(t7[i]+"  ");
			System.out.println();
		}
		System.out.println();
////////
		
////////PRINT		NewFaceConn
		itN = NewFaceConn.listIterator();
		while(itN.hasNext()){
			String[] t8 = (String[]) itN.next();
			for(i=0; i<t8.length; i++) System.out.print(t8[i]+"  ");
			System.out.println();
		}
		System.out.println();
////////		
				
//		create the face connectivity for the nodes/points above and below the
//		crack segment
	
		List<String[]> FaceAboveCrack = new ArrayList<String[]>();
		List<String[]> FaceBelowCrack = new ArrayList<String[]>();

		List<String> above = new ArrayList<String>();
		List<String> below = new ArrayList<String>();
		
////////PRINT		
		System.out.println("TARGET 1");
////////
		
		itN = NewFaceConn.listIterator();
		while(itN.hasNext()) {
			String[] actualFaceConnect = (String[]) itN.next();
			for (i = 0; i < actualFaceConnect.length; i++) { 
				String orientationN = (String) Abo.get(((Integer)connect.get(actualFaceConnect[i])).intValue());
				if (orientationN.equals("below") || orientationN.equals("on") || orientationN.equals("belowEdge") || orientationN.equals("aboveEdge")) {
//					node/point of the edge is below the (crack) segment
					String belowNode = new String();
					belowNode = actualFaceConnect[i];
					below.add(belowNode);
				} 
				if (orientationN.equals("above") || orientationN.equals("on") || orientationN.equals("belowEdge") || orientationN.equals("aboveEdge")) {
//					node/point of the edge is above the (crack) segment
					String aboveNode = new String();
					aboveNode = actualFaceConnect[i];
					above.add(aboveNode);
				}
			}
			
			if (below.size() == 2){
				String[] faceBelow = new String[below.size()];
				for(i=0; i<faceBelow.length; i++) faceBelow[i] = below.get(i);
				FaceBelowCrack.add(faceBelow);
			} 
			if (above.size() == 2){
				String[] faceAbove = new String[above.size()];
				for(i=0; i<faceAbove.length; i++) faceAbove[i] = above.get(i);
				FaceAboveCrack.add(faceAbove);
			}
			
			below.clear();
			above.clear();
		}
		
////////PRINT		
		System.out.println("FACE NODES BELOW CRACK");
		ListIterator itNbelow = FaceBelowCrack.listIterator();
		while(itNbelow.hasNext()){
			String[] t9 = (String[]) itNbelow.next();
			for(i=0; i<t9.length; i++) System.out.print(t9[i]+"  ");
			System.out.println();
		}
		System.out.println();
		
		System.out.println("FACE NODES ABOVE CRACK");
		ListIterator itNabove = FaceAboveCrack.listIterator();
		while(itNabove.hasNext()){
			String[] t10 = (String[]) itNabove.next();
			for(i=0; i<t10.length; i++) System.out.print(t10[i]+"  ");
			System.out.println();
		}
		System.out.println();
////////
////////PRINT		connect
		for(i=0; i<connect.size(); i++){
			Integer t11 = connect.get(connectMirror.get(i));
			System.out.print(t11);
			System.out.println();
		}
////////
		
////////PRINT		connectMirror
		for(i=0; i<connectMirror.size(); i++){
			String t12 = (String) connectMirror.get(i);
			System.out.print(t12);
			System.out.println();
		}
////////
		
//		creating the face ID and the connectivity map for the nodes/points on the
//		(crack) segment for the top and bottom edges
			
		List<String> unsorted = new ArrayList<String>();
		double[] vec1 = new double[3];
		double[] vec2 = new double[3];
		
		itO = Abo.listIterator();
		counter = 0; 
		
		while(itO.hasNext()) {
			String orientationN = (String)itO.next();
			if (orientationN.equals("on") || orientationN.equals("belowEdge") || orientationN.equals("aboveEdge")) {
				unsorted.add(connectMirror.get(counter));
			}
			counter++;
		}
		
		if (unsorted.size() != 2) assert false; // *ONLY* two points on the (crack) segment
		
		vec1 = (double[]) Coord.get((Integer)connect.get(unsorted.get(0)));
		vec2 = (double[]) Coord.get((Integer)connect.get(unsorted.get(1))); 
		xyz[0] = - (vec2[1] - vec1[1]);
		xyz[1] = vec2[0] - vec1[0];
		xyz[2] = 0.0;	
		
//		sort the nodes on the OnAbove surface of the crack so that the connectivity is 
//		correct -> a ccw connectivity results in a +ve sense; for the OnBelow surface too 
//		ccw connectivity results in a positive sense
		
		if (vecdotvec(xyz,m) > 0.0) { // keep the same order of the nodes
			above.add((String) unsorted.get(0)); 
			above.add((String) unsorted.get(1)); 
		}
		else { // switch the order of the nodes
			above.add((String) unsorted.get(1));
			above.add((String) unsorted.get(0));
		}
		
//		ccw connectivity for the OnBelow surface
		below.add(above.get(1));
		below.add(above.get(0));
		
//		create the edge OnAbove using the sorted points from vector above
		String[] unsortedFaceA = new String[above.size()];
		for(i=0; i<unsortedFaceA.length; i++) unsortedFaceA[i] = above.get(i);
		FaceAboveCrack.add(unsortedFaceA); 
		above.clear();
		
//		create the edge OnBelow using the sorted points from vector below
		
//		maxFaceId is updated in the case for OnAbove
		String[] unsortedFaceB = new String[below.size()];
		for(i=0; i<unsortedFaceB.length; i++) unsortedFaceB[i] = below.get(i);
		FaceBelowCrack.add(unsortedFaceB);  
		below.clear();
		
////////PRINT		
		System.out.println("FACE NODES BELOW CRACK");
		ListIterator itNbelow2 = FaceBelowCrack.listIterator();
		while(itNbelow2.hasNext()){
			String[] t13 = (String[]) itNbelow2.next();
			for(i=0; i<t13.length; i++) System.out.print(t13[i]+"  ");
			System.out.println();
		}
		System.out.println();
		
		System.out.println("FACE NODES ABOVE CRACK");
		ListIterator itNabove2 = FaceAboveCrack.listIterator();
		while(itNabove2.hasNext()){
			String[] t14 = (String[]) itNabove2.next();
			for(i=0; i<t14.length; i++) System.out.print(t14[i]+"  ");
			System.out.println();
		}
		System.out.println();
////////
		
//		create the centroid of the coordinates of the points/nodes below and above
//		the crack segment - the element is partitioned into triangles above and 
//		below the crack segment
		
		double[] below_centroid = new double[3];
		double[] above_centroid = new double[3];
		for(i=0; i<3; i++){
			below_centroid[i] = 0.0;
			above_centroid[i] = 0.0;
		}
		
		List<String> centroidConnect = new ArrayList<String>();
		itN = NewFaceConn.listIterator();
		counter = 0;
		while(itN.hasNext()){
			String[] cnn = (String[]) itN.next();
			for(i=0; i<cnn.length; i++){
				String nds = new String();
				nds = cnn[i];
				centroidConnect.add(nds);
			}
		}
		
		itO = Abo.listIterator();
		int nbabove = 0; int nbbelow = 0; counter = 0;
		while(itO.hasNext()){
			String ori = (String) itO.next();
			double[] xyzVector = new double[3];
			xyzVector = (double[]) Coord.get(counter);
			String nodeCon = connectMirror.get(counter);
			if(centroidConnect.contains(nodeCon)){
				if(ori.equals("below") || ori.equals("on") || ori.equals("belowEdge") || ori.equals("aboveEdge")){
					for(i=0, nbbelow++; i<3; i++) below_centroid[i] += xyzVector[i];
				}
				if(ori.equals("above") || ori.equals("on") || ori.equals("aboveEdge") || ori.equals("belowEdge")){
					for(i=0, nbabove++; i<3; i++) above_centroid[i] += xyzVector[i];
				}
			}
			counter++;
		}
		
		for (i = 0; i < 3; ++i) { 
			below_centroid[i] /= (double) nbbelow;
			above_centroid[i] /= (double) nbabove;
		}
		
////////PRINT
		System.out.println();
		System.out.println("CENTROID COORDINATES");
		System.out.println("BELOW AREA");
		for(i=0; i<3; i++) System.out.print(below_centroid[i]+"  ");
		System.out.println();
		System.out.println("ABOVE AREA");
		for(i=0; i<3; i++) System.out.print(above_centroid[i]+"  ");
		System.out.println();
		System.out.println();
////////
		
//		insert centroid into the coordinates and orientation maps (orientation +1000 and -1000
//		for points associated to the element area above and below the crack segment,
//		respectively)
		
		String aboveAreaPoint = "above_Centroid";
		connectMirror.add(aboveAreaPoint);
		connect.put(aboveAreaPoint,maxNodeId);
		
		orient = "aboveArea"; 
		Abo.add(orient);  
		
//		std::vector<double> centroid;
		Coord.add(above_centroid);  
		
		maxNodeId++;
		
		String belowAreaPoint = "below_Centroid";
		connectMirror.add(belowAreaPoint);
		connect.put(belowAreaPoint,maxNodeId);
		
		orient = "belowArea";  
//		int belowAreaPoint = maxNodeId;
		Abo.add(orient);   
		
		Coord.add(below_centroid);  
		
////////PRINT		Coord New
		itC = Coord.listIterator();
		while(itC.hasNext()){
			double[] t15 = (double[]) itC.next();
			for(i=0; i<3; i++) System.out.print(t15[i]+"  ");
			System.out.println();
		}
		System.out.println();
////////
////////PRINT		connect
		for(i=0; i<connect.size(); i++){
			Integer t16 = connect.get(connectMirror.get(i));
			System.out.print(t16);
			System.out.println();
		}
////////	
////////PRINT		connectMirror
		for(i=0; i<connectMirror.size(); i++){
			String t17 = (String) connectMirror.get(i);
			System.out.print(t17);
			System.out.println();
		}
////////
				
//		construct triangles (sub-elements)
//		map SubElements contains the element IDs and their connectivities; all sub-elements
//		that are a partition of the IxElement_c are contained in the map
		
		subElementsConnectAboveCrack = new ArrayList<List>();
		subElementsCoordsAboveCrack = new ArrayList<List>();
		subElementsConnectBelowCrack = new ArrayList<List>();
		subElementsCoordsBelowCrack = new ArrayList<List>();
		
		List<String> connvec = new ArrayList<String>();
		List<double[]> coorvec = new ArrayList<double[]>();
		
		ListIterator itFAC = FaceAboveCrack.listIterator();
		while(itFAC.hasNext()){
			String[] actualNewConnA = new String[2];
			actualNewConnA = (String[]) itFAC.next();
			String[] subconnA = new String[3];
			subconnA[0] = actualNewConnA[0];
			subconnA[1] = actualNewConnA[1];
			subconnA[2] = aboveAreaPoint;
			for(i=0; i<3; i++){
				double[] subcoorA = new double[3];
				subcoorA = (double[])Coord.get(((Integer)connect.get(subconnA[i])).intValue());
				coorvec.add(subcoorA);
				connvec.add(subconnA[i]);
			} 
			List<String> connvecAbove = new ArrayList<String>();
			connvecAbove.addAll(connvec);
			List<double[]> coorvecAbove = new ArrayList<double[]>();
			coorvecAbove.addAll(coorvec);
			subElementsConnectAboveCrack.add(connvecAbove);
			subElementsCoordsAboveCrack.add(coorvecAbove);
			connvec.clear();
			coorvec.clear();
		}
		
		ListIterator itFBC = FaceBelowCrack.listIterator();
		while(itFBC.hasNext()){
			String[] actualNewConnB = new String[2];
			actualNewConnB = (String[]) itFBC.next();
			String[] subconnB = new String[3];
			subconnB[0] = actualNewConnB[0];
			subconnB[1] = actualNewConnB[1];
			subconnB[2] = belowAreaPoint;
			for(i=0; i<3; i++){
				double[] subcoorB = new double[3];
				subcoorB = (double[])Coord.get(((Integer)connect.get(subconnB[i])).intValue());
				coorvec.add(subcoorB);
				connvec.add(subconnB[i]);
			} 
			List<String> connvecBelow = new ArrayList<String>();
			connvecBelow.addAll(connvec);
			List<double[]> coorvecBelow = new ArrayList<double[]>();
			coorvecBelow.addAll(coorvec);
			subElementsConnectBelowCrack.add(connvecBelow);
			subElementsCoordsBelowCrack.add(coorvecBelow);
			connvec.clear();
			coorvec.clear();
		}
			
		
	} //end of constructor class

	
//
//		 Functions
//		 =========
		
//	dot product of two vectors
//	double vecdotvec(double vec1[3], double vec2[3]); 
//
	protected double vecdotvec(double[] vec1, double[] vec2) {
		double res = 0.0;
		for (int k = 0; k < 3; k++) {
		  res += vec1[k] * vec2[k];
		}
		return res;
	}

//	tests if a point is ON, ABOVE, or BELOW the given segment
//	int OnAboveOrBelow(double px, double py, double pz, double p[3], double m[3]);
//
	protected String OnAboveOrBelow(double px, double py, double pz, double[] p, double[] m) { 
//		line equation in 2-D and that of the plane in 3-D
		double planeEq = m[0]*(px - p[0]) + m[1]*(py - p[1]) + m[2]*(pz - p[2]);
		  
		if (Math.abs(planeEq) <= tolerance) return "on"; 
		else if (planeEq > tolerance)       return "above";
		else                                return "below"; 
	}

//	determines the intersection of the given segment with the line joining p1 to p2
//	int LineIntersection(double p1x, double p1y, double p1z, 
//	                     double p2x, double p2y, double p2z,
//                       double& px, double& py, double& pz, 
//      			     double p0[3], double m[3]);
//
	protected boolean LineIntersection(double p1x, double p1y, double p1z, 
            			 			double p2x, double p2y, double p2z, 
            			 			double[] p0, double[] m) {

//  	point of intersection of a line (p1,p2) and a GxElement_c
//  	parametric representation of a line: p1 + t*(p2 - p1), where t = [0,1] if 
//  	there is an intersection

		double denominator = m[0]*(p1x - p2x) + m[1]*(p1y - p2y) + m[2]*(p1z - p2z);

		if (Math.abs(denominator) < tolerance) {
			System.out.println("\n Error: Line is either parallel to the plane or lies in the plane\n");
			assert false;
		}

		double t = (m[0]*(p1x - p0[0]) + m[1]*(p1y - p0[1]) + m[2]*(p1z - p0[2]))/denominator;

		if (t < 0.0 || t > 1.0) 
			return false;
		else {
			pointX = p1x + t*(p2x - p1x);
			pointY = p1y + t*(p2y - p1y);
			pointZ = p1z + t*(p2z - p1z);
		}
		return true;
	}
	
	protected double[] getNearPoint(Map nFaceCoords){
		Iterator itC = nFaceCoords.keySet().iterator();
		double[] initialNode = (double[]) itC.next();
		IPoint3d initNode = new IPoint3d(initialNode);
		double minorDist = 1.0e15;
		double[] nextNode = new double[3];
		while(itC.hasNext()){
			double[] actualNode = (double[]) itC.next();
			IPoint3d actNode = new IPoint3d(actualNode);
			double actualDist = initNode.distance(actNode);
			if(actualDist < minorDist){
				minorDist = actualDist;
				nextNode = actualNode;
			}
		}
		return nextNode;
	}


	/**
	 * @return Returns the subElementsConnectAboveCrack.
	 */
	public List getSubElementsConnectAboveCrack() {
		return subElementsConnectAboveCrack;
	}


	/**
	 * @return Returns the subElementsConnectBelowCrack.
	 */
	public List getSubElementsConnectBelowCrack() {
		return subElementsConnectBelowCrack;
	}


	/**
	 * @return Returns the subElementsCoordsAboveCrack.
	 */
	public List getSubElementsCoordsAboveCrack() {
		return subElementsCoordsAboveCrack;
	}


	/**
	 * @return Returns the subElementsCoordsBelowCrack.
	 */
	public List getSubElementsCoordsBelowCrack() {
		return subElementsCoordsBelowCrack;
	}
	
	public String toString(){
		
		DecimalFormat form = new DecimalFormat ("0.00E00");
		
		String result = "";
		
		List sECnAC = new ArrayList();
		sECnAC = this.getSubElementsConnectAboveCrack();
		ListIterator itCnAC = sECnAC.listIterator();
		
		List sECnBC = new ArrayList();
		sECnBC = this.getSubElementsConnectBelowCrack();
		ListIterator itCnBC = sECnBC.listIterator();
		
		List sECoAC = new ArrayList();
		sECoAC = this.getSubElementsCoordsAboveCrack();
		ListIterator itCoAC = sECoAC.listIterator();
		
		List sECoBC = new ArrayList();
		sECoBC = this.getSubElementsCoordsBelowCrack();
		ListIterator itCoBC = sECoBC.listIterator();
		
		int count = 0;
		
		result+= "\n        PARTITIONED  ELEMENT          \n\n";
		result+= "\n      SUBELEMENTS ABOVE CRACK         \n\n";
		while(itCnAC.hasNext()){
			count++;
			List cnac = (List) itCnAC.next();
			List coac = (List) itCoAC.next();
			ListIterator subItcnac = cnac.listIterator();
			ListIterator subItcoac = coac.listIterator();
			result+= "\n              SUBELEMENT "+count+"              \n\n";
			while(subItcnac.hasNext()){
				String subcnac = (String) subItcnac.next();
				double[] subcoac = (double[]) subItcoac.next();
				result+= "  "+subcnac+"  ";
				for(int i=0; i<3; i++) result+= "  "+form.format(subcoac[i]);
				result+= "\n";
			}
			result+= "\n";
		}
		count = 0;
		
		result+= "\n      SUBELEMENTS BELOW CRACK         \n\n";
		while(itCnBC.hasNext()){
			count++;
			List cnbc = (List) itCnBC.next();
			List cobc = (List) itCoBC.next();
			ListIterator subItcnbc = cnbc.listIterator();
			ListIterator subItcobc = cobc.listIterator();
			result+= "\n              SUBELEMENT "+count+"              \n\n";
			while(subItcnbc.hasNext()){
				String subcnbc = (String) subItcnbc.next();
				double[] subcobc = (double[]) subItcobc.next();
				result+= "  "+subcnbc+"  ";
				for(int i=0; i<3; i++) result+= "  "+form.format(subcobc[i]);
				result+= "\n";
			}
			result+= "\n";
		}

		return result;
	}
	
}//end of class Partitioning2D()
